﻿// poj2739 Sum of Consecutive Prime Numbers.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>

using namespace std;

/*

http://poj.org/problem?id=2739

连续素数之和
时间限制：1000MS 内存限制：65536K
总提交量。37460 被接受。19626
说明

一些正整数可以用一个或多个连续的素数之和来表示。一个给定的正整数有多少个这样的表示法？
例如，整数53有5+7+11+13+17和53两种表示法。整数41有三种表示方法：2+3+5+7+11+13，11+13+17，和41。
整数3只有一个表示，那就是3，整数20没有这种表示。请注意，和数必须是连续的质数

所以7+13或3+5+5+7都不是整数20的有效表示。
你的任务是编写一个程序，报告给定正整数的表示数。
输入

输入是一连串的正整数，每个都在一个单独的行中。这些整数在2和10 000之间，包括在内。输入的终点用一个零表示。
输出

输出应该由几行组成，每一行都对应于一个输入行，除了最后的零。一个输出行包括输入整数作为一个或多个连续素数之和的表示数。在输出中不应插入其他字符。
输入样本

2
3
17
41
20
666
12
53
0
样本输出

1
1
2
3
0
0
1
2
*/

const int N = 10010;
int primes[N], cnt;
bool st[N];

void get_primes(int n)
{
    for (int i = 2; i <= n; i++)
    {
        if (!st[i]) primes[cnt++] = i;
        for (int j = 0; primes[j] <= n / i; j++)
        {
            st[primes[j] * i] = true;
            if (i % primes[j] == 0) break;
        }
    }
}

void solve1(int n) {
    int l = cnt - 1; int r = l;
    int sum = primes[l]; int ans = 0;
    while (l >= 0 && r >= 0 && l <= r) {
        if (sum == n) {
            ans++; sum -= primes[r]; r--;
            if (sum == 0) {
                sum = primes[r]; l = r;
            }
        }
        else if (sum > n) {
            sum -= primes[r]; r--;
            if (sum == 0) {
                sum = primes[r]; l = r;
            }
        }
        else {
            l--; if (l < 0) { break; } 
            sum += primes[l];
        }
    }

    cout << ans << endl;
}

void solve(int n) {
    int l = 0; int r = 0;
    int sum = primes[0]; int ans = 0;
    while (l < cnt && r < cnt) {
        if (sum == n) {
            sum -= primes[l]; l++; ans++;
        }
        else if (sum > n) {
            sum -= primes[l]; l++;
        }
        else {
            r++;
            sum += primes[r];
        }
        if (sum == 0) { break; }
    }

    cout << ans << endl;
}

int main()
{
    get_primes(10001);

    while (1) {
        int n;
        cin >> n; if (n == 0) { break; }
        solve1(n);
   }

    return 0;
}

 